<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>剑指 Offer II 029. 排序的循环链表</title>
  </head>
  <body>
    <script>
      //     给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

      // 给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

      // 如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

      // 如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/4ueAj6
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * // Definition for a Node.
       * function Node(val, next) {
       *     this.val = val;
       *     this.next = next;
       * };
       */

      function Node(val, next) {
        this.val = val
        this.next = next
      }

      /**
       * @param {Node} head
       * @param {number} insertVal
       * @return {Node}
       */
      var insert = function (head, insertVal) {
        if (!head) {
          // 不存在节点，创建新的然后指向自己
          head = new Node(insertVal, null)
          head.next = head
          return head
        }
        if (head === head.next) {
          // 存在一个节点，直接新增节点，插入到下一位
          const node = new Node(insertVal, head)
          head.next = node
          return head
        }
        let now = head // 当前节点的地址
        let next = head.next // 下一节点的地址
        let nowVal = now.val // 当前节点的 val 值
        let nextVal = next.val // 下一节点的 val 值
        let min = head // 最小节点的地址
        let max = head // 最大节点的地址
        let isLimit = true // 插入的值是否为最大值或最小值
        do {
          if (insertVal >= nowVal && insertVal < nextVal) {
            // 如果插入值 > 当前节点值 && 插入值 < 下一节点值
            const node = new Node(insertVal, next) // 新建节点，插入当前节点和下一节点中
            now.next = node
            isLimit = false // 插入值不是最大值或最小值
            break
          }
          now = now.next // 指向下一节点
          next = next.next // 指向下下一节点
          nowVal = now.val // 指向下一节点的值
          nextVal = next.val // 指向下下一节点的值
          max = max.val > nowVal ? max : now // 寻找最大节点地址
          min = max.next // 最小节点地址
        } while (head !== now) // 是否完遍历一圈
        if (isLimit) {
          // 插入值为最大值或最小值
          const node = new Node(insertVal, min)
          max.next = node
        }
        return head
      }
      const head = new Node(3, null)
      const next = new Node(3, null)
      const end = new Node(3, null)
      head.next = next
      next.next = end
      end.next = head

      console.log(insert(head, 0))
    </script>
  </body>
</html>
